/**
 * \file Set.h
 * \brief Set definition and declaration class
 * \author Edouard ROGE
 * \date 13 september 2012
 */

#ifndef _SET_
#define _SET_

#include "ArrayBase.h"

/**
 * \class Set
 * \brief Set class with template, similar to std::set<T>
 */
template <class T>
class Set : public ArrayBase<T>
{
public:

	/** Set<T>::Iterator */
	typedef T*			Iterator;

	/** Set<T>::ConstIterator */
	typedef const T*	ConstIterator;

	/**
	 * \fn Set();
	 * \brief Default constructor
	 */
	Set();

	/**
	 * \fn Set(uint32 _iSize);
	 * \param _iSize new array's size
	 * \brief constructor, Resize array with the size in param
	 */
	Set(uint32 _iSize);

	/**
	 * \fn Set(const Set<T> & _tSet);
	 * \param _tSet array to copy
	 * \brief Copy constructor
	 */
	Set(const Set<T> & _tSet);

	/**
	 * \fn ~Set();
	 * \brief Destructor
	 */
	~Set();

	/**
	 * \fn void Insert(const T & _element);
	 * \param _element element to insert
	 * \brief insert an element to the position given by the iterator
	 */
	void Insert(const T & _element);

	/**
	 * \fn void Remove(const T & _element);
	 * \param _element element element to remove
	 * \brief remove an element from the array
	 */
	void Remove(const T & _element);

	/**
	 * \fn Iterator Begin();
	 * \return a pointer on the first element
	 * \brief Begin iterator
	 */
	Iterator Begin();

	/**
	 * \fn Iterator End();
	 * \return a pointer after the last element
	 * \brief End iterator
	 */
	Iterator End();

	/**
	 * \fn ConstIterator Begin() const;
	 * \return a pointer on the first element
	 * \brief Begin iterator
	 */
	ConstIterator Begin() const;

	/**
	 * \fn ConstIterator End() const;
	 * \return a pointer after the last element
	 * \brief End iterator
	 */
	ConstIterator End() const;

	/**
	 * \fn Iterator Find(const T & _element);
	 * \param _element element to find
	 * \return iterator pointing on this element if find, otherwise returns end iterator
	 * \brief find element in array
	 */
	Iterator Find(const T & _element);

	/**
	 * \fn ConstIterator Find(const T & _element)const;
	 * \param _element element to find
	 * \return iterator pointing on this element if find, otherwise returns end iterator
	 * \brief find element in array
	 */
	ConstIterator Find(const T & _element) const;

	/**
	 * \fn Set<T> & operator = (const Set<T> & _tSet);
	 * \param _tSet array to copy
	 * \return (*this) with new values
	 * \brief operator =
	 */
	Set<T> & operator = (const Set<T> & _tSet);

	/**
	 * \fn template< class S > friend bool operator == (const Set<S> & _tSet1, const Set<S> & _tSet2)
	 * \param _tSet1 array1
	 * \param _tSet2 array2
	 * \return true if array1 is equal to array2
	 * \brief operator ==
	 */
	template < class S > friend bool operator == (const Set<S> & _tSet1, const Set<S> & _tSet2);

	/**
	 * \fn template< class S > friend bool operator != (const Set<S> & _tSet1, const Set<S> & _tSet2)
	 * \param _tSet1 array1
	 * \param _tSet2 array2
	 * \return true if array1 is not equal to array2
	 * \brief operator !=
	 */
	template < class S > friend bool operator != (const Set<S> & _tSet1, const Set<S> & _tSet2);

private:

	/**
	 * \fn void _Insert(Iterator _begin, Iterator _end, const T & _element);
	 * \param _element element to insert
	 * \param _begin begin of the array
	 * \param _end end of the array
	 * \brief insert an element in array
	 */
	void _Insert(Iterator _begin, Iterator _end, const T & _element);

	/**
	 * \fn typename Set<T>::ConstIterator _Find(typename Set<T>::ConstIterator _begin, typename Set<T>::ConstIterator _end, const T & _element) const;
	 * \param _element element to find
	 * \param _begin begin of the array to find
	 * \param _end end of the array to find
	 * \return iterator pointing on this element if find, otherwise returns end iterator
	 * \brief find element in array
	 */
	typename Set<T>::ConstIterator _Find(typename Set<T>::ConstIterator _begin, typename Set<T>::ConstIterator _end, const T & _element) const;

	/**
	 * \fn typename Set<T>::Iterator _Find(typename Set<T>::Iterator _begin, typename Set<T>::Iterator _end, const T & _element);
	 * \param _element element to find
	 * \param _begin begin of the array to find
	 * \param _end end of the array to find
	 * \return iterator pointing on this element if find, otherwise returns end iterator
	 * \brief find element in array
	 */
	typename Set<T>::Iterator _Find(typename Set<T>::Iterator _begin, typename Set<T>::Iterator _end, const T & _element);

};


template< class T >
Set<T>::Set()
: ArrayBase<T>()
{
}

template< class T >
Set<T>::Set(uint32 _iSize)
: ArrayBase<T>(_iSize)
{
}

template< class T >
Set<T>::Set(const Set<T> & _tSet)
: ArrayBase<T>()
{
	_Clone(_tSet.m_tArray, _tSet.m_iSize);
}

template< class T >
Set<T>::~Set()
{
}

template< class T >
void Set<T>::Insert(const T & _element)
{
	if(ArrayBase<T>::Size()==0)
		ArrayBase<T>::_Insert(Begin(), _element);
	else
		Set<T>::_Insert(Begin(), End()-1, _element);
}

template< class T >
void Set<T>::Remove(const T & _element)
{
	Iterator it = Find(_element);
	if(it!=End())
		_Remove(it);
}

template< class T >
typename Set<T>::Iterator Set<T>::Begin()
{
	return ArrayBase<T>::m_tArray;
}

template< class T >
typename Set<T>::Iterator Set<T>::End()
{
	return (ArrayBase<T>::m_tArray + ArrayBase<T>::m_iSize);
}

template< class T >
typename Set<T>::ConstIterator Set<T>::Begin() const
{
	return ArrayBase<T>::m_tArray;
}

template< class T >
typename Set<T>::ConstIterator Set<T>::End() const
{
	return (ArrayBase<T>::m_tArray + ArrayBase<T>::m_iSize);
}

template< class T >
typename Set<T>::Iterator Set<T>::Find(const T & _element)
{
	if(ArrayBase<T>::Size()==0)
		return End();
	else
		return _Find(Begin(), End(), _element);
}

template< class T >
typename Set<T>::ConstIterator Set<T>::Find(const T & _element)const
{
	if(ArrayBase<T>::Size()==0)
		return End();
	else
		return _Find(Begin(), End()-1, _element);
}

template< class T >
void Set<T>::_Insert(typename Set<T>::Iterator _begin, typename Set<T>::Iterator _end, const T & _element)
{
	uint32 iSize = _end - _begin;

	if(iSize==0)
	{
		// element already exists
		if(_element!=(*_begin))
			ArrayBase<T>::_Insert(_begin+(_element<(*_begin)?0:1), _element);

		return;
	}

	Set<T>::Iterator treshold = _begin + (iSize+(iSize&1))/2;

	if(iSize==1)
		(_element<(*_end)?Set<T>::_Insert(_begin, _begin, _element):Set<T>::_Insert(_end, _end, _element));
	else
		(_element<=(*treshold)?Set<T>::_Insert(_begin, treshold, _element):Set<T>::_Insert(treshold, _end, _element));
}

template< class T >
typename Set<T>::Iterator Set<T>::_Find(typename Set<T>::Iterator _begin, typename Set<T>::Iterator _end, const T & _element)
{
	uint32 iSize = _end - _begin;

	if(iSize==0)
	{
		// element already exists
		if(_element!=(*_begin))
			return Set<T>::End();
		else
			return _begin;
	}

	Set<T>::Iterator treshold =_begin + (iSize+(iSize&1))/2;
	if(iSize==1)
		return (_element<(*_end)?Set<T>::_Find(_begin, _begin, _element):Set<T>::_Find(_end, _end, _element));
	else
		return (_element<(*treshold)?Set<T>::_Find(_begin, treshold, _element):Set<T>::_Find(treshold, _end, _element));
}

template< class T >
typename Set<T>::ConstIterator Set<T>::_Find(typename Set<T>::ConstIterator _begin, typename Set<T>::ConstIterator _end, const T & _element) const
{
	uint32 iSize = _end - _begin;

	if(iSize==0)
	{
		// element already exists
		if(_element!=(*_begin))
			return Set<T>::End();
		else
			return _begin;
	}

	Set<T>::ConstIterator treshold = _begin + (iSize+(iSize&1))/2;

	if(iSize==1)
		return (_element<(*treshold)?Set<T>::_Find(_begin, _begin, _element):Set<T>::_Find(_end, _end, _element));
	else
		return (_element<(*treshold)?Set<T>::_Find(_begin, treshold, _element):Set<T>::_Find(treshold, _end, _element));
}

template< class T >
Set<T> & Set<T>::operator = (const Set<T> & _tSet)
{
	_Clone(_tSet.m_tArray, _tSet.m_iSize);
	return (*this);
}

/**
 * \fn template< class S > bool operator == (const Set<S> & _tSet1, const Set<S> & _tSet2)
 * \param _tSet1 array1
 * \param _tSet2 array2
 * \return true if array1 is equal to array2
 * \brief operator ==
 */
template< class S >
bool operator == (const Set<S> & _tSet1, const Set<S> & _tSet2)
{
	uint32 iSize1 = _tSet1.Size();
	if( iSize1 == _tSet2.Size() )
	{
		for(uint32 i=0; i < iSize1; ++i)
			if( _tSet1[i] != _tSet2[i] )
				return false;

		return true;
	}

	return false;
}

/**
 * \fn template< class S > bool operator != (const Set<S> & _tSet1, const Set<S> & _tSet2)
 * \param _tSet1 array1
 * \param _tSet2 array2
 * \return true if array1 is not equal to array2
 * \brief operator !=
 */
template< class S >
bool operator != (const Set<S> & _tSet1, const Set<S> & _tSet2)
{
	return !(_tSet1 == _tSet2);
}

#endif // _SET_
